<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>(933)最近请求次数 | Oliver知识收集站</title>
    <meta name="generator" content="VuePress 1.9.7">
    
    <meta name="description" content="享受着互联网广泛知识，并加以记录，日积月累让它成为一个档案处！">
    <meta name="viewport" content="width=device-width,initial-scale=1,user-scalable=no">
    
    <link rel="preload" href="/oliver-vuepress/assets/css/0.styles.4ea20d86.css" as="style"><link rel="preload" href="/oliver-vuepress/assets/js/app.c21e6ffc.js" as="script"><link rel="preload" href="/oliver-vuepress/assets/js/3.6dd9a2a1.js" as="script"><link rel="preload" href="/oliver-vuepress/assets/js/1.898920d0.js" as="script"><link rel="preload" href="/oliver-vuepress/assets/js/12.8607f0e1.js" as="script"><link rel="prefetch" href="/oliver-vuepress/assets/js/10.41b2bf91.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/11.a95c117d.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/13.a52d6846.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/14.249b4e52.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/15.d458d12e.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/16.ba334206.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/17.1b91c9fa.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/18.e2ea2eb5.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/19.bf0e2553.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/20.268bd174.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/21.cd1bbed5.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/22.da4bc7f7.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/23.12f0c72f.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/24.b7886742.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/25.6e71af85.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/26.5c127243.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/27.e98fd8bf.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/28.ce83b09c.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/29.50398f0f.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/30.05e1339c.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/31.ef4b13fb.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/32.ba5f8351.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/33.3902db0a.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/34.36a05884.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/35.87215872.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/36.db360c58.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/37.402e5374.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/38.c9228dd8.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/39.72ba5d1f.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/4.7bb03d47.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/40.7e7949bf.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/41.c0d5b947.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/42.d9984467.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/43.e6a43668.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/44.10d7fe47.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/45.f692ec2d.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/46.9b920343.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/47.8e3d94f9.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/48.7d356e5b.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/49.b0df6271.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/5.1fa544da.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/50.805e1466.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/51.1b31d40e.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/52.44e69a41.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/53.da1def53.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/54.6569f7db.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/55.5fc3de47.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/56.da649377.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/57.6ff15ed4.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/58.a62f6424.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/59.f68ae517.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/6.f5bd8e9b.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/60.dda416bc.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/61.4e0c719f.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/62.8c5ef01e.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/63.7089eb8b.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/64.b5ec150d.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/65.6720cda4.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/66.4ee90e29.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/67.cc4b0c6d.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/7.d5950c53.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/8.382fb3a5.js"><link rel="prefetch" href="/oliver-vuepress/assets/js/9.d593f4c1.js">
    <link rel="stylesheet" href="/oliver-vuepress/assets/css/0.styles.4ea20d86.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container" data-v-130b300a><div data-v-130b300a><div class="password-shadow password-wrapper-out" style="display:none;" data-v-25ba6db2 data-v-130b300a data-v-130b300a><h3 class="title" data-v-25ba6db2 data-v-25ba6db2>Oliver知识收集站</h3> <p class="description" data-v-25ba6db2 data-v-25ba6db2>享受着互联网广泛知识，并加以记录，日积月累让它成为一个档案处！</p> <label id="box" class="inputBox" data-v-25ba6db2 data-v-25ba6db2><input type="password" value="" data-v-25ba6db2> <span data-v-25ba6db2>Konck! Knock!</span> <button data-v-25ba6db2>OK</button></label> <div class="footer" data-v-25ba6db2 data-v-25ba6db2><span data-v-25ba6db2><i class="iconfont reco-theme" data-v-25ba6db2></i> <a target="blank" href="https://vuepress-theme-reco.recoluan.com" data-v-25ba6db2>vuePress-theme-reco</a></span> <span data-v-25ba6db2><i class="iconfont reco-copyright" data-v-25ba6db2></i> <a data-v-25ba6db2><span data-v-25ba6db2>oliver.shi</span>
            
          <!---->
          2022
        </a></span></div></div> <div class="hide" data-v-130b300a><header class="navbar" data-v-130b300a><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/oliver-vuepress/" class="home-link router-link-active"><!----> <span class="site-name">Oliver知识收集站</span></a> <div class="links"><div class="color-picker"><a class="color-button"><i class="iconfont reco-color"></i></a> <div class="color-picker-menu" style="display:none;"><div class="mode-options"><h4 class="title">Choose mode</h4> <ul class="color-mode-options"><li class="dark">dark</li><li class="auto active">auto</li><li class="light">light</li></ul></div></div></div> <div class="search-box"><i class="iconfont reco-search"></i> <input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><a href="/oliver-vuepress/" class="nav-link"><i class="undefined"></i>
  主页
</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title"><i class="undefined"></i>
      Java
    </span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/java/basics/" class="nav-link"><i class="undefined"></i>
  基础
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/java/concurrent/" class="nav-link"><i class="undefined"></i>
  并发
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/java/jvm/jvm.html" class="nav-link"><i class="undefined"></i>
  JVM
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/java/other/" class="nav-link"><i class="undefined"></i>
  杂
</a></li></ul></div></div><div class="nav-item"><a href="/oliver-vuepress/articles/spring/first.html" class="nav-link"><i class="undefined"></i>
  Spring
</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title"><i class="undefined"></i>
      中间件
    </span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/middleware/redis/redis.html" class="nav-link"><i class="undefined"></i>
  Redis
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/middleware/kafka/framework.html" class="nav-link"><i class="undefined"></i>
  Kafka
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/middleware/zookeeper.html" class="nav-link"><i class="undefined"></i>
  Zookeeper
</a></li></ul></div></div><div class="nav-item"><a href="/oliver-vuepress/articles/algorithm/" class="nav-link router-link-active"><i class="undefined"></i>
  算法
</a></div><div class="nav-item"><a href="/oliver-vuepress/timeline/" class="nav-link"><i class="iconfont reco-date"></i>
  TimeLine
</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title"><i class="undefined"></i>
      收集站
    </span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/collect/article/first.html" class="nav-link"><i class="undefined"></i>
  技术好文
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/collect/book/first.html" class="nav-link"><i class="undefined"></i>
  书籍
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/collect/assembly/first.html" class="nav-link"><i class="undefined"></i>
  优秀开发组件
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/collect/software/first.html" class="nav-link"><i class="undefined"></i>
  软件
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/collect/plugin/first.html" class="nav-link"><i class="undefined"></i>
  插件
</a></li></ul></div></div> <!----></nav></div></header> <div class="sidebar-mask" data-v-130b300a></div> <aside class="sidebar" data-v-130b300a><div class="personal-info-wrapper" data-v-39576ba9 data-v-130b300a><!----> <h3 class="name" data-v-39576ba9>
    oliver.shi
  </h3> <div class="num" data-v-39576ba9><div data-v-39576ba9><h3 data-v-39576ba9>52</h3> <h6 data-v-39576ba9>Articles</h6></div> <div data-v-39576ba9><h3 data-v-39576ba9>6</h3> <h6 data-v-39576ba9>Tags</h6></div></div> <ul class="social-links" data-v-39576ba9></ul> <hr data-v-39576ba9></div> <nav class="nav-links"><div class="nav-item"><a href="/oliver-vuepress/" class="nav-link"><i class="undefined"></i>
  主页
</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title"><i class="undefined"></i>
      Java
    </span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/java/basics/" class="nav-link"><i class="undefined"></i>
  基础
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/java/concurrent/" class="nav-link"><i class="undefined"></i>
  并发
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/java/jvm/jvm.html" class="nav-link"><i class="undefined"></i>
  JVM
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/java/other/" class="nav-link"><i class="undefined"></i>
  杂
</a></li></ul></div></div><div class="nav-item"><a href="/oliver-vuepress/articles/spring/first.html" class="nav-link"><i class="undefined"></i>
  Spring
</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title"><i class="undefined"></i>
      中间件
    </span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/middleware/redis/redis.html" class="nav-link"><i class="undefined"></i>
  Redis
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/middleware/kafka/framework.html" class="nav-link"><i class="undefined"></i>
  Kafka
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/middleware/zookeeper.html" class="nav-link"><i class="undefined"></i>
  Zookeeper
</a></li></ul></div></div><div class="nav-item"><a href="/oliver-vuepress/articles/algorithm/" class="nav-link router-link-active"><i class="undefined"></i>
  算法
</a></div><div class="nav-item"><a href="/oliver-vuepress/timeline/" class="nav-link"><i class="iconfont reco-date"></i>
  TimeLine
</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title"><i class="undefined"></i>
      收集站
    </span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/collect/article/first.html" class="nav-link"><i class="undefined"></i>
  技术好文
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/collect/book/first.html" class="nav-link"><i class="undefined"></i>
  书籍
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/collect/assembly/first.html" class="nav-link"><i class="undefined"></i>
  优秀开发组件
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/collect/software/first.html" class="nav-link"><i class="undefined"></i>
  软件
</a></li><li class="dropdown-item"><!----> <a href="/oliver-vuepress/articles/collect/plugin/first.html" class="nav-link"><i class="undefined"></i>
  插件
</a></li></ul></div></div> <!----></nav> <ul class="sidebar-links"><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading open"><span>算法</span> <span class="arrow down"></span></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/oliver-vuepress/articles/algorithm/933.html" aria-current="page" class="active sidebar-link">(933)最近请求次数</a></li><li><a href="/oliver-vuepress/articles/algorithm/1021.html" class="sidebar-link">(1021删)除最外层的括号</a></li></ul></section></li></ul> </aside> <div class="password-shadow password-wrapper-in" style="display:none;" data-v-25ba6db2 data-v-130b300a><h3 class="title" data-v-25ba6db2 data-v-25ba6db2>(933)最近请求次数</h3> <!----> <label id="box" class="inputBox" data-v-25ba6db2 data-v-25ba6db2><input type="password" value="" data-v-25ba6db2> <span data-v-25ba6db2>Konck! Knock!</span> <button data-v-25ba6db2>OK</button></label> <div class="footer" data-v-25ba6db2 data-v-25ba6db2><span data-v-25ba6db2><i class="iconfont reco-theme" data-v-25ba6db2></i> <a target="blank" href="https://vuepress-theme-reco.recoluan.com" data-v-25ba6db2>vuePress-theme-reco</a></span> <span data-v-25ba6db2><i class="iconfont reco-copyright" data-v-25ba6db2></i> <a data-v-25ba6db2><span data-v-25ba6db2>oliver.shi</span>
            
          <!---->
          2022
        </a></span></div></div> <div data-v-130b300a><main class="page"><section><div class="page-title"><h1 class="title">(933)最近请求次数</h1> <div data-v-f875f3fc><i class="iconfont reco-account" data-v-f875f3fc><span data-v-f875f3fc>oliver.shi</span></i> <i class="iconfont reco-date" data-v-f875f3fc><span data-v-f875f3fc>8/9/2021</span></i> <!----> <i class="tags iconfont reco-tag" data-v-f875f3fc><span class="tag-item" data-v-f875f3fc>算法</span></i></div></div> <div class="theme-reco-content content__default"><h2 id="题目"><a href="#题目" class="header-anchor">#</a> 题目：</h2> <p>写一个RecentCounter类来计算特定时间范围内最近的请求。</p> <p>请你实现 RecentCounter 类：</p> <p>RecentCounter() 初始化计数器，请求数为 0 。
int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。
保证 每次对 ping 的调用都使用比之前更大的 t 值。</p> <h2 id="实例"><a href="#实例" class="header-anchor">#</a> 实例：</h2> <div class="language- extra-class"><pre class="language-text"><code>输入：
[&quot;RecentCounter&quot;, &quot;ping&quot;, &quot;ping&quot;, &quot;ping&quot;, &quot;ping&quot;]
[[], [1], [100], [3001], [3002]]
输出：
[null, 1, 2, 3, 3]

解释：
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // requests = [1]，范围是 [-2999,1]，返回 1
recentCounter.ping(100);   // requests = [1, 100]，范围是 [-2900,100]，返回 2
recentCounter.ping(3001);  // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3
recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3

</code></pre></div><img src="/oliver-vuepress/java/algorithm/933-提示.jpg"> <h2 id="实现方案1-遍历数组-暴利破解"><a href="#实现方案1-遍历数组-暴利破解" class="header-anchor">#</a> 实现方案1： 遍历数组 （暴利破解）</h2> <p>解题思路：</p> <ul><li>将每次请求的数，存放到数组中 （并记录最后一位的下标）</li> <li>每次从数组尾部进行遍历，对大于等于 【t - 3000】 ，进行统计次数，进行累加</li></ul> <div class="language-Java extra-class"><pre class="language-java"><code><span class="token keyword">class</span> <span class="token class-name">RecentCounter</span> <span class="token punctuation">{</span>
	
 	  <span class="token class-name">List</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">Integer</span><span class="token punctuation">&gt;</span></span> list <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">ArrayList</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">Integer</span><span class="token punctuation">&gt;</span></span><span class="token punctuation">(</span><span class="token number">10000</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token keyword">public</span> <span class="token class-name">RecentCounter</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

    <span class="token punctuation">}</span>

    <span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">ping1</span><span class="token punctuation">(</span><span class="token keyword">int</span> t<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        list<span class="token punctuation">.</span><span class="token function">add</span><span class="token punctuation">(</span>t<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> end <span class="token operator">=</span> list<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> count <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span>list<span class="token punctuation">.</span><span class="token function">get</span><span class="token punctuation">(</span>end<span class="token punctuation">)</span> <span class="token operator">&gt;=</span> t <span class="token operator">-</span> <span class="token number">3000</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            count<span class="token operator">++</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">--</span>end <span class="token operator">&lt;</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> count<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><h2 id="实现方案2-优化-遍历数组"><a href="#实现方案2-优化-遍历数组" class="header-anchor">#</a> 实现方案2： 优化 - 遍历数组</h2> <p>优化思路：</p> <ul><li>确认3000 毫秒内 最多请求数 ？——&gt;  用去减少数组的存储空间
<ul><li>t 请求次 + 前3000次 = 3001次</li> <li>但 数组需要设置成  3002 次 （因为是先写入数据，在删除）</li></ul></li> <li>统计是是否需要进行遍历所有的节点，来计算出数组的的次数？ ——&gt; 减少不必要的循环
<ul><li>每次添加时，循环遍历数组，将数组内不符合范围内的数据给删除</li> <li>最后 列表中只剩下符合条件的请求次数，直接获取 <code>size()</code> 即可</li></ul></li></ul> <div class="language-java extra-class"><pre class="language-java"><code>
<span class="token keyword">class</span> <span class="token class-name">RecentCounter</span> <span class="token punctuation">{</span>
	
 	  <span class="token class-name">List</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">Integer</span><span class="token punctuation">&gt;</span></span> list <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">ArrayList</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">Integer</span><span class="token punctuation">&gt;</span></span><span class="token punctuation">(</span><span class="token number">3002</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token keyword">public</span> <span class="token class-name">RecentCounter</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
		
    <span class="token punctuation">}</span>

    <span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">ping1</span><span class="token punctuation">(</span><span class="token keyword">int</span> t<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        list<span class="token punctuation">.</span><span class="token function">add</span><span class="token punctuation">(</span>t<span class="token punctuation">)</span><span class="token punctuation">;</span>
		   <span class="token keyword">while</span> <span class="token punctuation">(</span>list<span class="token punctuation">.</span><span class="token function">get</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span> <span class="token operator">&lt;</span> t <span class="token operator">-</span> <span class="token number">3000</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    			list<span class="token punctuation">.</span><span class="token function">remove</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
		   <span class="token punctuation">}</span>
		   <span class="token keyword">return</span> list<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><h2 id="实现方案3-队列解法"><a href="#实现方案3-队列解法" class="header-anchor">#</a> 实现方案3： 队列解法</h2> <h3 id="_3-1-自定义队列-底层使用链表"><a href="#_3-1-自定义队列-底层使用链表" class="header-anchor">#</a> 3-1： 自定义队列 （底层使用链表）</h3> <p>解题思路：</p> <ul><li>使用队列的数据结构，先进先出的原则
<ul><li>通过链表实现队列</li> <li>定义属性： 对头：<code>head</code> 、对尾： <code>tail</code> 、长度： <code>size</code></li> <li>定义方法： 添加节点：<code>add()</code>  、移除节点:  <code>poll()</code> 、 队列长度： <code>size()</code></li> <li>内部定义： <code>Node</code> 类 ，封装每次入队的请求，和指向下一个节点的指针</li></ul></li> <li>每次请求向队列尾部追加节点</li> <li>循环检查列头数据是否合法，不合法则移除节点</li> <li>返回队列长度</li></ul> <div class="language-java extra-class"><pre class="language-java"><code>
<span class="token keyword">class</span> <span class="token class-name">RecentCounter</span> <span class="token punctuation">{</span>

    <span class="token class-name">Queue</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">Integer</span><span class="token punctuation">&gt;</span></span> q <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">LinkedList</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">Integer</span><span class="token punctuation">&gt;</span></span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token keyword">public</span> <span class="token class-name">RecentCounter</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

    <span class="token punctuation">}</span>

    <span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">ping</span><span class="token punctuation">(</span><span class="token keyword">int</span> t<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        q<span class="token punctuation">.</span><span class="token function">add</span><span class="token punctuation">(</span>t<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span>q<span class="token punctuation">.</span>head<span class="token punctuation">.</span><span class="token function">getVal</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&lt;</span> t <span class="token operator">-</span> <span class="token number">3000</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            q<span class="token punctuation">.</span><span class="token function">poll</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
       <span class="token keyword">return</span> q<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">class</span> <span class="token class-name">Queue</span> <span class="token punctuation">{</span>
        <span class="token class-name">Node</span> head<span class="token punctuation">;</span>

        <span class="token class-name">Node</span> tail<span class="token punctuation">;</span>

        <span class="token keyword">int</span> size <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>

        <span class="token class-name">Queue</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

        <span class="token punctuation">}</span>

        <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">add</span><span class="token punctuation">(</span><span class="token keyword">int</span> val<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>head <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                head <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token punctuation">(</span>val<span class="token punctuation">)</span><span class="token punctuation">;</span>
                tail <span class="token operator">=</span> head<span class="token punctuation">;</span>
            <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
                <span class="token class-name">Node</span> last <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token punctuation">(</span>val<span class="token punctuation">)</span><span class="token punctuation">;</span>
                tail<span class="token punctuation">.</span>next <span class="token operator">=</span> last<span class="token punctuation">;</span>
                tail <span class="token operator">=</span> last<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            size<span class="token operator">++</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">poll</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">int</span> headVal <span class="token operator">=</span> head<span class="token punctuation">.</span>val<span class="token punctuation">;</span>
            <span class="token class-name">Node</span> next <span class="token operator">=</span> head<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
            head<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
            head <span class="token operator">=</span> next<span class="token punctuation">;</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>next <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                tail <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            size<span class="token operator">--</span><span class="token punctuation">;</span>
            <span class="token keyword">return</span> headVal<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>


        <span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>


        <span class="token keyword">class</span> <span class="token class-name">Node</span> <span class="token punctuation">{</span>
            <span class="token keyword">int</span> val<span class="token punctuation">;</span>
            <span class="token class-name">Node</span> next<span class="token punctuation">;</span>

            <span class="token class-name">Node</span><span class="token punctuation">(</span><span class="token keyword">int</span> index<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                <span class="token keyword">this</span><span class="token punctuation">.</span>val <span class="token operator">=</span> index<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>

            <span class="token keyword">int</span> <span class="token function">getVal</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                <span class="token keyword">return</span> val<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

</code></pre></div><h3 id="_3-2-使用java提供的队列"><a href="#_3-2-使用java提供的队列" class="header-anchor">#</a> 3-2： 使用Java提供的队列</h3> <p>解题逻辑与 自定义逻辑一致。
其实Java 原生就提供的 链表 和 队列的实现 没有必要太多的自定义:</p> <div class="language-java extra-class"><pre class="language-java"><code>
<span class="token keyword">class</span> <span class="token class-name">RecentCounter</span> <span class="token punctuation">{</span>

    <span class="token class-name">Queue</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">Integer</span><span class="token punctuation">&gt;</span></span> q <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">LinkedList</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">Integer</span><span class="token punctuation">&gt;</span></span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token keyword">public</span> <span class="token class-name">RecentCounter</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

    <span class="token punctuation">}</span>

    <span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">ping</span><span class="token punctuation">(</span><span class="token keyword">int</span> t<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        q<span class="token punctuation">.</span><span class="token function">add</span><span class="token punctuation">(</span>t<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span>q<span class="token punctuation">.</span><span class="token function">peek</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&lt;</span> t <span class="token operator">-</span> <span class="token number">3000</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            q<span class="token punctuation">.</span><span class="token function">poll</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> q<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>


</code></pre></div></div></section> <footer class="page-edit"><!----> <div class="last-updated"><span class="prefix">上次更新: </span> <span class="time">4/21/2022, 8:17:59 AM</span></div></footer> <div class="page-nav"><p class="inner"><!----> <span class="next"><a href="/oliver-vuepress/articles/algorithm/1021.html">
            (1021删)除最外层的括号
          </a></span></p></div> <div class="comments-wrapper"><!----></div> <ul class="side-bar sub-sidebar-wrapper" style="width:12rem;" data-v-cb1513f6><li class="level-2" data-v-cb1513f6><a href="/oliver-vuepress/articles/algorithm/933.html#题目" class="sidebar-link reco-side-题目" data-v-cb1513f6>题目：</a></li><li class="level-2" data-v-cb1513f6><a href="/oliver-vuepress/articles/algorithm/933.html#实例" class="sidebar-link reco-side-实例" data-v-cb1513f6>实例：</a></li><li class="level-2" data-v-cb1513f6><a href="/oliver-vuepress/articles/algorithm/933.html#实现方案1-遍历数组-暴利破解" class="sidebar-link reco-side-实现方案1-遍历数组-暴利破解" data-v-cb1513f6>实现方案1： 遍历数组 （暴利破解）</a></li><li class="level-2" data-v-cb1513f6><a href="/oliver-vuepress/articles/algorithm/933.html#实现方案2-优化-遍历数组" class="sidebar-link reco-side-实现方案2-优化-遍历数组" data-v-cb1513f6>实现方案2： 优化 - 遍历数组</a></li><li class="level-2" data-v-cb1513f6><a href="/oliver-vuepress/articles/algorithm/933.html#实现方案3-队列解法" class="sidebar-link reco-side-实现方案3-队列解法" data-v-cb1513f6>实现方案3： 队列解法</a></li><li class="level-3" data-v-cb1513f6><a href="/oliver-vuepress/articles/algorithm/933.html#_3-1-自定义队列-底层使用链表" class="sidebar-link reco-side-_3-1-自定义队列-底层使用链表" data-v-cb1513f6>3-1： 自定义队列 （底层使用链表）</a></li><li class="level-3" data-v-cb1513f6><a href="/oliver-vuepress/articles/algorithm/933.html#_3-2-使用java提供的队列" class="sidebar-link reco-side-_3-2-使用java提供的队列" data-v-cb1513f6>3-2： 使用Java提供的队列</a></li></ul></main> <!----></div></div></div></div><div class="global-ui"><div class="back-to-ceiling" style="right:1rem;bottom:6rem;width:2.5rem;height:2.5rem;border-radius:.25rem;line-height:2.5rem;display:none;" data-v-c6073ba8 data-v-c6073ba8><svg t="1574745035067" viewBox="0 0 1024 1024" version="1.1" xmlns="http://www.w3.org/2000/svg" p-id="5404" class="icon" data-v-c6073ba8><path d="M526.60727968 10.90185116a27.675 27.675 0 0 0-29.21455937 0c-131.36607665 82.28402758-218.69155461 228.01873535-218.69155402 394.07834331a462.20625001 462.20625001 0 0 0 5.36959153 69.94390903c1.00431239 6.55289093-0.34802892 13.13561351-3.76865779 18.80351572-32.63518765 54.11355614-51.75690182 118.55860487-51.7569018 187.94566865a371.06718723 371.06718723 0 0 0 11.50484808 91.98906777c6.53300375 25.50556257 41.68394495 28.14064038 52.69160883 4.22606766 17.37162448-37.73630017 42.14135425-72.50938081 72.80769204-103.21549295 2.18761121 3.04276886 4.15646224 6.24463696 6.40373557 9.22774369a1871.4375 1871.4375 0 0 0 140.04691725 5.34970492 1866.36093723 1866.36093723 0 0 0 140.04691723-5.34970492c2.24727335-2.98310674 4.21612437-6.18497483 6.3937923-9.2178004 30.66633723 30.70611158 55.4360664 65.4791928 72.80769147 103.21549355 11.00766384 23.91457269 46.15860503 21.27949489 52.69160879-4.22606768a371.15156223 371.15156223 0 0 0 11.514792-91.99901164c0-69.36717486-19.13165746-133.82216804-51.75690182-187.92578088-3.42062944-5.66790279-4.76302748-12.26056868-3.76865837-18.80351632a462.20625001 462.20625001 0 0 0 5.36959269-69.943909c-0.00994388-166.08943902-87.32547796-311.81420293-218.6915546-394.09823051zM605.93803103 357.87693858a93.93749974 93.93749974 0 1 1-187.89594924 6.1e-7 93.93749974 93.93749974 0 0 1 187.89594924-6.1e-7z" p-id="5405" data-v-c6073ba8></path><path d="M429.50777625 765.63860547C429.50777625 803.39355007 466.44236686 1000.39046097 512.00932183 1000.39046097c45.56695499 0 82.4922232-197.00623328 82.5015456-234.7518555 0-37.75494459-36.9345906-68.35043303-82.4922232-68.34111062-45.57627738-0.00932239-82.52019037 30.59548842-82.51086798 68.34111062z" p-id="5406" data-v-c6073ba8></path></svg></div></div></div>
    <script src="/oliver-vuepress/assets/js/app.c21e6ffc.js" defer></script><script src="/oliver-vuepress/assets/js/3.6dd9a2a1.js" defer></script><script src="/oliver-vuepress/assets/js/1.898920d0.js" defer></script><script src="/oliver-vuepress/assets/js/12.8607f0e1.js" defer></script>
  </body>
</html>
